// 递归函数

// 递归函数的简单案例：计算 1 加到 n 的和（n>=1）

// 实现分析

// 1. 先封装一个函数 sum(n)，然后找出临界值，如果n==1时，就直接返回1
// 2. 接着先假设计算到100的和，其实就是用 sum(99) + 100，即前 99 的和加上 100.
// 这样可以得出 1 加到 100 的公式，sum(100) = sum(100-1) + 100
// sum(n) = sum(n-1) + n
// 3. return 这个公式

function sum(n) {
    if(n == 1) {
        return 1;
    }
    return sum(n-1) + n;
}

console.log(sum(100));
console.log(sum(3));

// 经典递归问题案例：爬楼梯问题

function f(n) {
    if(n == 1 || n == 2) {
        return n;
    }
    return f(n-1) + f(n-2);
}

console.log(f(2)); // 2

console.log(f(6)); // 13

console.log(f(20)); // 10946